The invention is related to the field of Electronic Design Automation, and more particularly, to a method of optimizing the design of an integrated circuit chip or system in the presence of uncertainty in the modeling or predictability of the design variables and functions, by reducing the number of design functions at limiting values in the final design.
A wide variety of methods are employed in the optimization of integrated circuit designs. These techniques attempt to improve the design (i.e., to minimize some overall design cost or objective function) while meeting a set of constraints. Examples of design constraints include limits on the total silicon area occupied by the circuit, limits on the amount of power which can be consumed by the circuit, limits on the noise (i.e., unintended signals occurring on nets within the design due to such things as coupling from other wires) on any net in the design, and limits on the maximum path delay through the circuit (and hence on the maximum clock frequency and minimum clock period at which the circuit can operate). Each of these parameters may also contribute to the overall design objective function which is to be minimized. By way of example, a design objective may be to minimize (rather than to limit) the maximum path delay through the circuit, the area occupied by the circuit, the power consumed by the circuit, or some combination of these functions.
In many cases, the limits imposed by constraints are not absolute limits, but instead represent engineering judgment regarding the point beyond which the constrained function will unduly impact the correctness, reliability, performance, or other aspects of the design. Thus, these constraints are not hard, meaning that the design will fail if they are not met, and minor violations of the constraints may be acceptable. In many optimization methods, constraints are modeled as part of the objective function. In such instances, a constraint contributes nothing to the design objective if it is met, but violation of the constraint causes a large increase in the objective function, often proportional to the magnitude of the violation or to some power (e.g., the square) of the magnitude of the violation. Note that even a design objective which is to be maximized may be represented as part of an objective function to be minimized by suitable transformation, e.g., by including its negative (or for functions which are strictly greater than zero, its inverse) as part of the minimization objective. Where the ensuing description refers to minimizing an objective function it should be understood to include such transformations.
Many different methods can be used to optimize a design. Domain-specific heuristic search techniques can be used to propose a variety of small changes to a design which are expected, due to domain knowledge, to improve the objective function. One or more of these proposed change which gives the greatest reduction in the objective function is then chosen and implemented. This process is repeated until no further improvement is possible or until the processing time allowed for optimization has been exhausted.
Simulated annealing techniques optimize a system by a method analogous to process of annealing a physical material. Such methods propose a random change to a design, determine the increase or decrease in the objective function due to the change, accept all proposed changes which decrease the objective function, and only accept changes which increase the objective function according to a probability function related to the amount of increase in the objective function. This process is repeated many times, and a xe2x80x9ctemperaturexe2x80x9d parameter is slowly decreased during the optimization process, causing the probability of accepting objective function-degrading changes to decrease until, at the end, only objective function-improving changes are accepted. Further details about simulated annealing are described in U.S. Pat. No. 4,495,559 to Gelatt Jr. et al.
Numerical optimization techniques, as described, e.g., in the publication entitled xe2x80x9cLANCELOT: A Fortran Package for Large-Scale Nonlinear Optimizationxe2x80x9d by A. R. Conn, et al., Springer-Verlag, 1992, use numerical methods to minimize an objective function represented as a function of a set of problem variables. Allowed ranges are defined for problem variables, and a set of constraints is given, each specifying that some linear or nonlinear function of some group of problem variables is less than zero (Note: any inequality constraint between functions of variables of a design can be converted to this form). The optimizer attempts to minimize the objective function subject to the imposed constraints by varying the problem variables within their allowed ranges. This type of optimization is often referred to as design tuning. Details of this technique may be found in an article entitled xe2x80x9cGradient-based optimization of custom circuits using a static-timing formulationxe2x80x9d by A. R. Conn, et al., Proceedings of the 1999 IEEE/ACM Design Automation Conference. The inequality constraints are often converted to equality constraints by introducing constraint slack variables which are required to be greater than or equal to zero. For example, the following constraint (in which f and g are functions and x, y, z, u, v, and w are design variables):
f(x,y,z)xe2x89xa7g(u,v,w,x)
can be converted to the following by the introduction of constraint slack variable s:
0=s+f(x,y,z)xe2x88x92g(u,v,w,x),
sxe2x89xa70
In many instances, the design objective function or some component thereof, will be the maximum of some set of functions of design variables. For example, if the objective is to minimize the longest path delay in a circuit, the value to be minimized will be the maximum of the path delay over all circuit paths, where each of these delays is a function of design variables such as transistor widths and wire widths. Optimization problems with objectives of this nature are often referred to as minimax problems, the variable to be minimized is the minimax variable, and constraints involving it are called minimax constraints. In a numerical optimization framework, assume that the set of design functions involved include f1, . . . , fn and the associated minimax variable representing the maximum of these values is z. The problem will then be to minimize z (or some monotonically increasing function of z) subject to constraints:
zxe2x89xa7f1
zxe2x89xa7fn
Similarly, a design objective function may include a variable to be maximized which is itself the minimum of some set of functions of design variables. Such a problem and variable are referred to as a maximin problem and variable, respectively, and can be transformed to a minimax problem and variable by negating the maximin variable and all functions constraining it. Hereinafter references to minimax problems and variables will be understood to include maximin problems and variables transformed in this manner.
There are multiple ways of modeling a design constraint or objective function involving the maximum (or minimum) delay through a circuit. One method is to identify every possible path through the integrated circuit and to constrain the delay of each identified path to be less than a limit. But the number of paths through a circuit can be very large, potentially growing exponentially with the size of the circuit, thus introducing an enormous number of constraints into the optimization problem.
An alternative method is to use a node-oriented static timing analysis algorithm as described, e.g., in U.S. Pat. No. 4,263,651 to Donath et al. Therein, a timing graph is created with nodes representing points in the network at which digital signal transitions (typically voltage transitions between ground and the supply voltage Vdd) occur and edges representing the dependencies between these nodes, so that an edge is present from node X to node Y if and only if, under some circumstances, a signal transition at X can directly cause a signal transition at Y. A late mode arrival time (AT) is computed at each node in the timing graph representing the latest time within the machine clock cycle at which a signal transition at the node can stabilize (reach the final value for the current machine cycle), and an early mode AT is computed at each node in the timing graph representing the earliest time within the machine clock cycle at which a signal transition at the node can become unstable (change from the value taken on at the end of the previous machine cycle). Nodes with no incoming edges are considered primary inputs (PIs) of the design and have fixed (not variable) ATs asserted by the designer. Optionally, required arrival times (RATs) can be computed at each node in the timing graph, with a late mode RAT representing the latest time that a signal transition can arrive at the node and still have its propagated consequences stabilize early enough at all network outputs to meet the design timing requirements, and an early mode RAT representing the earliest time that a signal transition can arrive at the node and still allow all network outputs to remain stable long enough to meet the design timing requirements. Nodes with no outgoing edges are considered primary outputs (POs) of the design and have fixed (not variable) RATs asserted by the designer. Consider a node n with incoming edges ei1, . . . , ein from nodes i1, . . . , in, respectively, with corresponding minimum delays di1min, . . . , dinmin, and maximum delays di1max, . . . , dinmax, and with outgoing edges eo1, . . . , eon to nodes o1, . . . , on, respectively, with corresponding minimum delays do1min, . . . , donmin, and maximum delays do1max, . . . , donmax. This is illustrated in FIG. 1. For node n, ATs are computed as:
ATlate(n)=max(ATlate(i1)+di1max, . . . ATlate(in)+dinmax)
ATearly(n)=min(ATearly(i1)+di1min, . . . ATearly(in)+dinmin)
and RATs are computed as:
RATlate(n)=min(RATlate(o1)xe2x88x92do1max, . . . RATlate(on)xe2x88x92donmax)
RATearly(n)=max(RATearly(o1)xe2x88x92do1min, . . . RATearly(on)xe2x88x92donmin)
In a numerical optimizer, these relationships can be represented as constraints. For example, the early and late mode ATs of n would be involved in the following constraints:
Atearly(n)xe2x89xa6ATearly(i1)+di1min
Atearly(n)xe2x89xa6ATearly(in)+dinmin
Atearly(o1)xe2x89xa6ATearly(n)+do1min
Atearly(on)xe2x89xa6ATearly(n)+donmin
Atlate(n)xe2x89xa7ATlate(i1)+di1max
Atlate(n)xe2x89xa7ATlate(in)+dinmax
Atlate(o1)xe2x89xa7ATlate(n)+do1max
Atlate(on)xe2x89xa7ATlate(n)+donmax
Early and late mode timing slacks (not to be confused with constraint slacks in numerical optimization) can be defined at a node as follows, so that a negative slack always indicates the violation of a timing requirement:
Slack_late(n)=RATlate(n)xe2x88x92ATlate(n)
Slack_early(n)=ATearly(n)xe2x88x92RATearly(n)
Numerical optimizers operate most efficiently if the number of constraints and variables in the problem is minimized. When representing a late mode timing problem as a set of constraints, it is often possible to reduce both the number of variables and constraints by eliminating ATlate constraints. This process is called pruning, which is described in detail in U.S. Pat. No. 6,321,362 to Conn et al.
By way of example, consider a timing graph in which an edge exy from node X to node Y with delay dxy is the only incoming edge of node Y and an edge eyz from node Y to node Z with delay dyz is the only outgoing edge of node Y. Then the ATlate(Y) variable can be eliminated and constraints:
ATlate(Y)xe2x89xa7ATlate(X)+dxy
ATlate(Z)xe2x89xa7ATlate(Y)+dyz
can be replaced by the single constraint
ATlate(Z)xe2x89xa7ATlate(X)+dxy+dyz
This is illustrated in FIG. 2.
In many instances, an optimization objective is to minimize the cycle time of the design. If the late mode timing slacks at all POs are positive, the nominal cycle time of the machine, T0 (relative to which the PO RAT values were specified), can be reduced by the minimum of these positive slack values. Thus, if the set of POs of the design is PO1, . . . POn and the cycle time to be minimized is T, this implies the following minimax constraints:
RATlate(PO1)xe2x89xa7ATlate(PO1)+T0xe2x88x92T
RATlate(POn)xe2x89xa7ATlate(POn)+T0xe2x88x92T
It is possible, and often advantageous, to prune ATlate variables for POs, just as for other nodes in the timing graph. For example, if PO node S has incoming edges from nodes Q and R with delays dqs and dqr, respectively, constraints:
ATlate(S)xe2x89xa7ATlate(Q)+dqs
ATlate(S)xe2x89xa7ATlate(R)+drs
RATlate(S)xe2x89xa7ATlate(S)+T0xe2x88x92T
can be replaced by constraints
RATlate(S)xe2x89xa7ATlate(Q)+dqs+T0xe2x88x92T
RATlate(S)xe2x89xa7ATlate(R)+drs+T0xe2x88x92T
In a numerical optimizer, it can occur that a variable is not at one of its limits and has no constraint which directly limits its value. For example, if a circuit contains nodes X, Y, and Z with delay edges from X to Y and from Y to Z, the delay from X to Y and from Y to Z each have maximum values of 1, ATlate(X)=0, and ATlate(Z)=3 (due to some other incoming edge to Z, then variable ATlate(Y) can take on any value from 1 to 2 without affecting the optimization result. This situation is called xe2x80x9cdegeneracyxe2x80x9d of the variable, and can cause undesirable behavior in a numerical optimizer. Degeneracy of design constraints can also occur when a constraint is tight (i.e., the constraint slack is zero) but does not directly affect the objective function (i.e., the constraint slack can be increased without increasing the objective function), because no xe2x80x9cchainxe2x80x9d of other tight constraints exists to xe2x80x9ctransmitxe2x80x9d changes in the constraint slack to the objective function. Thus, it is advantageous to reduce the degeneracy in problems posed to numerical optimizer.
It is possible that a design optimization method fails to reduce the design objective function to an acceptable value. For example, if the design objective function is (or includes) the achievable cycle time of the design, the optimization process may end with a cycle time which is larger than desired. Typically, in such cases a designer will apply other manual methods which are unknown to or were not considered by the optimizer to further improve the design objective function. It is therefore desirable that the portion of the design which needs to be improved (e.g., the number of POs whose AT values do not satisfy the desired cycle time) be as small as possible, to reduce the manual effort required by the designer.
Often an optimizer will have both upward and downward pressure on a design function or variable. For example, the delay of an edge in a timing graph may be inversely related to the size of one or more transistors in the circuit, and the sum of the size of all the transistors in the design may be constrained not to exceed a value or it may be a component of the overall objective function. The optimizer will then attempt to reduce the size of the transistors, thereby increasing delays as long as it does not violate another constraint or impact the objective function. Assuming that the optimization objective is to minimize the cycle time T, and some critical path in the design causes a lower limit on T of Tmin (i.e., the slack along this path cannot be increased above T0xe2x88x92Tmin). If the ATlate constraints are formulated as above, the incentive to increase delays combined with the ATlate constraints will cause, for primary output pj, ATlate(pj) to increase until it equals
RATlate(pj)xe2x88x92T0+Tmin,
and the constraint slack of the minimax constraint in which it is involved is zero. The optimizer will have an incentive to reduce these ATlate variables (and hence T) only if all of them can be reduced together and, thus, all PO late mode ATs will increase to equal the one that is hardest to reduce. This is achieved by paying large costs (e.g., making large increases in transistor widths) along the critical path(s), appropriating this cost from non-critical paths (e.g., reducing transistor widths, thereby increasing delays along non-critical paths in order to obey a constraint on the sum of all transistor widths). As a result very large delay increases may occur along non-critical paths in order to achieve minuscule delay decreases along the critical path(s). The result of such an optimization is shown in FIG. 3. The horizontal axis represents the late mode timing slack, and the vertical axis represents the cumulative number of POs whose timing slack is less than the horizontal axis slack. It can be seen that the optimization process has created a xe2x80x9cslack wall,xe2x80x9d where most POs have been tuned to a slack of about 24 (those with higher slacks had other constraints which limited the increase in the delays of the paths feeding them).
Unfortunately, the basis upon which the design is optimized has its limitations. Static timing and other analysis methods make a number of simplifying assumptions. The prediction of parasitic electrical parameters upon which delay and other aspects of circuit behavior depend may be less than perfect. Model-to-hardware correlation problems often arise. The design may undergo further modification after the optimization program has completed. Unpredictable variations may cause circuit parameters to change from their nominal values. Variations can be due to manufacturing process or environmental variations (e.g., supply voltage or temperature). If the modeling of the problem in the optimizer is not exact, or the modeled parameters are not exactly predictable, the actual values which a design parameter will take in any given manufactured instance of the design may best be considered as a random variable whose value is described by probability distribution function (PDF) rather than a specific value. For example, a PO late mode AT which is modeled as having value 10 may in reality take on a range of values from 8 to 12 in different manufactured instances and different operating conditions.
In the face of all this uncertainty, having a slack wall of equally timing critical POs is undesirable, since simple statistical principles predict that when each value in the slack wall is a random variable, the expected maximum of these values is larger when the height of the wall is greater. In a paper titled xe2x80x9cIncrease in Delay Uncertainty by Performance Optimizationxe2x80x9d published in the Proceedings of the 2001 International Symposium on Circuits and Systems, M. Hashimoto et al. show that it is possible for careful optimization of a circuit to actually degrade the performance due to manufacturing variations, and demonstrate the impact of the height of the slack wall.
One method for handling this problem is to attempt to more accurately model the values and distributions of design parameters. This requires that the entire optimization process deal with design parameters as random variables rather than as scalar values. It is not clear how to apply existing techniques to such a model, and where it is possible, it would drastically increase the complexity and runtime of the optimization process. For example, the simple act of taking the maximum of two random variables requires a convolution (a double-integration process) to compute the resulting PDF.
In view of the foregoing, there is a need for a method to improve the expected value for the objective function of a design by reducing the number of design constraints which will be at limiting values in the final design without explicitly modeling the variation in design parameters.
Thus, it is an object of the invention to provide a method for reducing the number of design constraints which will be at the limiting values of the final design in the presence of uncertainty in the modeling of design parameters.
It is another object to provide a method for decreasing the expected cost of a design whose objective function includes a plurality of minimax constraints in the presence of uncertainty in the modeling of design parameters.
It is still another object to provide a method for decreasing the expected cost of a design by way of numerical optimization in the presence of uncertainty in the modeling of design parameters.
It is yet another object to provide a method for reducing the degeneracy of design numerical optimization problems.
It is a further object to provide a method for reducing the number of design constraints which are violated at the end of the optimization process, in the event that all design constraints cannot be satisfied.
It is a more particular object to reduce the cycle time at which a design can operate in the presence of uncertainty in the modeling of design parameters.
It is still a further object to reduce the increase in the minimum operational cycle time of a particular implementation of the design in the presence of variations that cannot be modeled or unpredictable variations in any of the delays of the elements of the design.
In one aspect of the invention, there is described a method for optimizing or tuning high performance digital circuits or electronic systems. Existing optimization techniques provide a plurality of paths deemed to be equally critical. These optimization methods are often unable to account for manufacturing and environmental variations. To these variations are to be added inaccurate modeling, all of which introduce a degree of uncertainty that adversely affects the expected performance of the circuit or system. Further, the large number of critical paths being singled out makes the process of further manual optimization of the circuit or system and cumbersome.
The present invention modifies the way of tuning the circuits or system by sensitizing the design to account for the aforementioned uncertainty. At a cost of a negligible price in the nominal system performance, the number of equally critical paths is reduced substantially and a separation is achieved between the most critical paths and the remaining paths. Thus, the resulting design is less sensitive and less likely to be affected by manufacturing variations and the like, making the downstream restructuring of the circuit or system much easier.
In another aspect of the invention, an extra penalty is added to the objective function for each primary output of the design, such that increasing the separation between the slack of the primary output and the worst slack, curtails the size of the penalty. This penalty forces the optimizer to obtain the necessary separation and facilitate the optimization process.
The present invention provides a method for optimizing the design of a chip or system that includes the steps of: defining an objective function computed from variables of the design of the chip or system; deriving a merit function from the objective function by adding to the objective function a plurality of separation terms; and minimizing the merit function which reduces the expected value of the objective function in the presence of variations of the design variables.
The invention further provides a method for optimizing the design of a chip or system by minimizing the expected cycle time at which the chip or system can operate, the method comprising the steps of: defining an objective function as the nominal value of the minimum cycle time at which the chip or system can operate computed as a function of the design parameters of the design; deriving a merit function from the objective function by adding to the objective function a plurality of separation terms, each of the separation terms being a function of the difference between two quantities associated with a node or edge of a timing graph of the design; and minimizing the merit function which reduces the expected value of the objective function in the presence of variations of the design parameters.